1.11 Ejemplo de lista abierta en C++ usando plantillas:  

El siguiente paso es usar plantillas (templates) para definir listas genéricas, cuyos nodos pueden ser objetos de cualquier tipo definido en nuestro programa.

El código es algo más complicado, al menos a primera vista. Pero comprobaremos que es mucho más flexible y versatil.

Seguimos necesitando dos clases, una para nodo y otra para lista. Pero ahora podremos usar esas clases para construir listas de cualquier tipo de datos. Además, definiremos la clase para nodo como local dentro de la clase para lista, de ese modo nos evitamos definir amistades entre clases. A fin de cuentas, la clase nodo sólo la usaremos en esta lista.

Código del un ejemplo completo:

Es preferible declarar cada plantilla clase en un fichero independiente, de este modo podremos usarlas en otros programas fácilmente. Empezamos con una plantilla para lista:

// ListaAb.h: Plantilla para lista abierta ordenada
// C con Clase. (C) Marzo de 2002
// Plantilla para lista abierta
// Posibles mejoras:
// * Implementar constructor copia.

#ifndef _LISTAABIERTA_
#define _LISTAABIERTA_

template<class DATO>
class Lista {
  private:
   //// Clase local de Lista para Nodo de Lista:
   template<class DATON>
   class Nodo {
     public:
      // Constructor:
      Nodo(const DATON dat, Nodo<DATON> *sig) : dato(dat), siguiente(sig) {}
      // Miembros:
      DATON dato;
      Nodo<DATON> *siguiente;
   };

   // Punteros de la lista, para cabeza y nodo actual:
   Nodo<DATO> *primero;
   Nodo<DATO> *actual;

  public:
   // Constructor y destructor básicos:
   Lista() : primero(NULL), actual(NULL) {}
   ~Lista();
   // Funciones de inserción:
   void InsertarFinal(const DATO dat);
   void InsertarPrincipio(const DATO dat);
   bool InsertarActual(const DATO dat);
   void Insertar(const DATO dat);
   // Funciones de borrado:
   void BorrarActual();
   bool BorrarPrimerValor(const DATO dat);
   // Función de búsqueda:
   bool BuscarPrimerValor(const DATO dat);
   // Comprobar si la lista está vacía:
   bool Vacia() { return primero==NULL; }
   // Devolver referencia al dato del nodo actual:
   DATO &ValorActual() { return actual->dato; }
   // Hacer que el nodo actual sea el primero:
   void Primero() { actual = primero; }
   // Comprobar si el nodo actual es válido:
   bool Actual() { return actual != NULL; }
   // Moverse al siguiente nodo de la lista:
   void Siguiente() { if(actual) actual = actual->siguiente; }
   // Sobrecargar operator++ en forma sufija para los mismo:
   void operator++(int) { Siguiente(); }
   // Aplicar una función a cada elemento de la lista:
   void ParaCada(void (*func)(DATO&));
};

//////// Implementación:

// Destructor
template<class DATO>
Lista<DATO>::~Lista() {
   while(!Vacia()) {
      actual = primero;
      primero = primero->siguiente;
      delete actual;
   }
}

template<class DATO>
void Lista<DATO>::InsertarFinal(const DATO dat) {
   Nodo<DATO> *ultimo;

   // Si la lista está vacía, insertar al principio:
   if(Vacia()) InsertarPrincipio(dat);
   else { // Si no lo está:
      // Buscar el último nodo:
      ultimo = primero;
      while(ultimo->siguiente) ultimo = ultimo->siguiente;
      // Insertar a continuación:
      ultimo->siguiente = new Nodo<DATO>(dat, NULL);
   }
}

template<class DATO>
void Lista<DATO>::InsertarPrincipio(const DATO dat) {
   primero = new Nodo<DATO>(dat, primero);
}

template<class DATO>
bool Lista<DATO>::InsertarActual(const DATO dat) {
   // Sólo si la lista no está vacía y actual es válido:
   if(!Vacia() && actual) {
      actual->siguiente = new Nodo<DATO>(dat, actual->siguiente);
      return true;
   }
   // Si no se puede insertar, retornar con false:
   return false;
}

// Insertar ordenadamente:
template<class DATO>
void Lista<DATO>::Insertar(const DATO dat) {
   Nodo<DATO> *temp = primero;
   Nodo<DATO> *anterior = NULL;

   // Si la lista está vacía, insertar al principio:
   if(Vacia()) InsertarPrincipio(dat);
   else {
      // Buscar el nodo anterior al primer nodo con un dato mayor qur 'dat'
      while(temp && temp->dato < dat) {
         anterior = temp;
         temp = temp->siguiente;
      }
      // Si no hay anterior, insertar al principio,
      // nuestro valor es el menor de la lista:
      if(!anterior)
         InsertarPrincipio(dat);
      else // Insertar:
         anterior->siguiente = new Nodo<DATO>(dat, temp);
   }
}

template<class DATO>
void Lista<DATO>::BorrarActual() {
   Nodo<DATO> *anterior;

   // Si el nodo actual es el primero:
   if(actual && actual == primero) {
      // El primer nodo será ahora el segundo:
      // Sacar el nodo actual de la lista:
      primero = actual->siguiente;
      // Borrarlo:
      delete actual;
      actual = NULL;
   } else
   if(actual && !Vacia()) {
      // Buscar el nodo anterior al actual:
      anterior = primero;
      while(anterior && anterior->siguiente != actual)
         anterior = anterior->siguiente;
      // Sacar el nodo actual de la lista:
      anterior->siguiente = actual->siguiente;
      // Borrarlo:
      delete actual;
      actual = NULL;
   }
}

// Borrar el primer nodo cuyo dato sea igual a 'dat':
template<class DATO>
bool Lista<DATO>::BorrarPrimerValor(const DATO dat) {
   Nodo<DATO> *anterior = NULL;
   Nodo<DATO> *temp = primero;

   if(!Vacia()) {
      // Si la lista no está vacía, buscar el nodo a borrar (temp)
      // y el nodo anterior a ese (anterior):
      while(temp && temp->dato != dat) {
         anterior = temp;
         temp = temp->siguiente;
      }
      // Si el valor está en la lista:
      if(temp) {
         // Si anterior es válido, no es el primer valor de la lista
         if(anterior) // Sacar nodo temp de la lista
            anterior->siguiente = temp->siguiente;
         else         // Ahora el primero es el segundo:
           primero = temp->siguiente;  // Borrar primer elemento
         // Borrar nodo:
         delete temp;
         return true; // Se ha encontrado y borrado dat
      }
   }
   return false; // valor no encontrado
}

// Busca el primer nodo con valor 'dat':
template<class DATO>
bool Lista<DATO>::BuscarPrimerValor(const DATO dat) {
   actual = primero;

   // Si la lista no está vacía:
   if(!Vacia()) {
      while(actual && actual->dato != dat) {
         actual = actual->siguiente;
      }
   }
   // Si el nodo es válido, se ha encontrado el valor:
   return actual != NULL;
}

// Aplicar una función a cada nodo de la lista:
template<class DATO>
void Lista<DATO>::ParaCada(void (*func)(DATO&)) {
   Nodo<DATO> *temp = primero;

   // Recorrer la lista:
   while(temp) {
      // Aplicar la función:
      func(temp->dato);
      temp = temp->siguiente;
   }
}

// La función "func" debe ser una plantilla de una función
// que no retorne valor y que admita un parámetro del mismo
// tipo que la lista:
// template <class DATO>
// void <funcion>(DATO d);

#endif

Hemos introducido algunos refinamientos en nuestra clase que la harán más fácil de usar. Por ejemplo:

• Cuatro versiones distintas para insertar nodos, una para insertar al principio, otra al final, otra a continuación del nodo actual y una cuarta para insertar por orden. Ésta última nos permite crear listas ordenadas.
• Dos funciones para borrar valores, una borra el elemento actual y la otra el primer nodo que contenga el valor especificado.
• Sobrecarga del operador de postincremento, que nos permite movernos a lo largo de la lista de un modo más intuitivo.
• Función "ParaCada", que aplica una función a cada elemento de la lista. Veremos cómo podemos usar esta función para hacer cosas como mostrar la lista completa o incrementar todos los elementos.

En el tema de plantillas del curso de C++ ya hemos visto que existen algunas limitaciones para los tipos que se pueden emplear en plantillas. Por ejemplo, no podemos crear una lista de cadenas usando Lista<char *>, ya que de ese modo sólo creamos una lista de punteros.

Para poder crear listas de cadenas hemos implementado una clase especial para cadenas, en la que además de encapsular las cadenas hemos definido los operadadores =, ==, !=, >, <, >=, <=, algunos de los cuales son necesarios para poder crear listas con esta clase.

Clase para manejar cadenas:

// CCadena.h: Fichero de cabecera de definición de cadenas
// C con Clase: Marzo de 2002

#ifndef CCADENA
#define CCADENA
#include <cstring>
using namespace std;

class Cadena {
  public:
   Cadena(char *cad) {
      cadena = new char[strlen(cad)+1];
      strcpy(cadena, cad);
   }
   Cadena() : cadena(NULL) {}
   Cadena(const Cadena &c) : cadena(NULL) {*this = c;}
   ~Cadena() { if(cadena) delete[] cadena; }
   Cadena &operator=(const Cadena &c) {
      if(this != &c) {
         if(cadena) delete[] cadena;
         if(c.cadena) {
            cadena = new char[strlen(c.cadena)+1];
            strcpy(cadena, c.cadena);
         }
         else cadena = NULL;
      }
      return *this;
   }
   bool operator==(const Cadena &c) const {
      return !strcmp(cadena, c.cadena);
   }
   bool operator!=(const Cadena &c) const {
      return strcmp(cadena, c.cadena);
   }
   bool operator<(const Cadena &c) const {
      return strcmp(cadena, c.cadena) < 0;
   }
   bool operator>(const Cadena &c) const {
      return strcmp(cadena, c.cadena) > 0;
   }
   bool operator<=(const Cadena &c) const {
      return strcmp(cadena, c.cadena) <= 0;
   }
   bool operator>=(const Cadena &c) const {
      return strcmp(cadena, c.cadena) >= 0;
   }

   const char* Lee() const {return cadena;}
   
  private:
   char *cadena;
};

ostream& operator<<(ostream &os, const Cadena& cad) {
   os << cad.Lee();
   return os;
}
#endif

Ahora ya podemos poner algunos ejemplos de listas creadas con plantillas:

// ListaAb.cpp: Ejemplo de uso de plantilla para listas abiertas
// C con Clase: Marzo de 2002

#include <iostream>
#include "CCadena.h"
#include "ListaAb.h"
using namespace std;
 
// Plantilla de función que incrementa el valor del objeto
// dado como parámetro aplicando el operador ++
template<class DATO>
void Incrementar(DATO &d) {
   d++;
}

// Plantilla de función que mustra el valor del objeto
// dado como parámetro formando una lista separada con comas
template<class DATO>
void Mostrar(DATO &d) {
   cout << d << ", ";
}

int main() {
   // Declaración de una lista de enteros:
   Lista<int> ListaInt;

   // Inserción de algunos valores:
   ListaInt.InsertarFinal(43);
   ListaInt.InsertarFinal(65);
   ListaInt.InsertarFinal(33);
   ListaInt.InsertarFinal(64);
   ListaInt.InsertarFinal(22);
   ListaInt.InsertarFinal(11);

   // Mostrar lista:
   cout << "---listado---" << endl;
   ListaInt.ParaCada(Mostrar); // Aplicamos la función Mostrar a cada elemento
   cout << endl << "-------------" << endl;

   // Incrementamos los valores de todos los elementos de la lista
   // aplicando a cada uno la función "Incrementar":
   cout << "---Incrementar todos---" << endl;
   ListaInt.ParaCada(Incrementar);

   // Mostrar lista:
   cout << "---listado---" << endl;
   ListaInt.ParaCada(Mostrar);
   cout << endl << "-------------" << endl;
   cin.get();

   // Borrar el primer elemento de valor 34:
   cout << "borrar 34" << endl;
   ListaInt.BorrarPrimerValor(34);

   // Mostrar lista:
   cout << "---listado---" << endl;
   ListaInt.ParaCada(Mostrar);
   cout << endl << "-------------" << endl;

   // Declaración de una lista de floats:
   Lista<float> ListaFloat;

   // Inserción de algunos valores:
   ListaFloat.InsertarFinal(43.2);
   ListaFloat.InsertarFinal(65.3);
   ListaFloat.InsertarFinal(33.1);
   ListaFloat.InsertarFinal(64.8);
   ListaFloat.InsertarFinal(22.32);
   ListaFloat.InsertarFinal(11.003);

   // Mostrar lista:
   cout << "---listado---" << endl;
   ListaFloat.ParaCada(Mostrar);
   cout << endl << "-------------" << endl;

   // Incrementamos todos:
   cout << "---Incrementar todos---" << endl;
   ListaFloat.ParaCada(Incrementar);

   // Mostrar lista:
   cout << "---listado---" << endl;
   ListaFloat.ParaCada(Mostrar);
   cout << endl << "-------------" << endl;

   cin.get();

   // Declaración de una lista de cadenas:
   Lista<Cadena> ListaCad;

   // Inserción de algunos valores, creando una lista ordenada:
   ListaCad.Insertar("alfa");
   ListaCad.Insertar("delta");
   ListaCad.Insertar("beta");
   ListaCad.Insertar("gamma");
   ListaCad.Insertar("delta");
   ListaCad.Insertar("epsilon");
   ListaCad.Insertar("sigma");
   ListaCad.Insertar("delta");

   // Mostrar lista:
   cout << "---listado---" << endl;
   ListaCad.ParaCada(Mostrar);
   cout << endl << "-------------" << endl;
   cin.get();

   // Borramos todos los elementos de valor "delta":
   while(ListaCad.BorrarPrimerValor("delta")) {
      cout << "borrar 'delta'" << endl;
      // Mostrar lista:
      cout << "---listado---" << endl;
      ListaCad.ParaCada(Mostrar);
      cout << endl << "-------------" << endl;
      cin.get();
   }

   // Buscar el primer elemento de valor "gamma":
   cout << "buscar 'gamma'" << endl;
   if(ListaCad.BuscarPrimerValor("gamma"))
      cout << ListaCad.ValorActual() << endl;
   else
      cout << "No encontrado" << endl;

   // Declaración de una lista de enteros:
   Lista<int> ListaOrden;

   // Inserción de algunos valores, creando una lista ordenada:
   cout << "Lista ordenada de enteros" << endl;
   ListaOrden.Insertar(43);
   ListaOrden.Insertar(65);
   ListaOrden.Insertar(33);
   ListaOrden.Insertar(64);
   ListaOrden.Insertar(4);
   ListaOrden.Insertar(22);
   ListaOrden.Insertar(1);
   ListaOrden.Insertar(11);
   ListaOrden.Insertar(164);

   // Mostrar lista:
   cout << "---listado---" << endl;
   ListaOrden.ParaCada(Mostrar);
   cout << endl << "-------------" << endl;

   cin.get();
   return 0;
}

Hemos creado dos plantillas de funciones para demostrar el uso de la función "ParaCada", una de ellas incrementa cada valor de la lista, la otra lo muestra por pantalla. La primera no puede aplicarse a listas de cadenas, porque el operador ++ no está definido en la clase Cadena.

El resto creo que no necesita mucha explicación.

Fichero con el código fuente.